#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
  int jump(vector<int> &nums) {
    // jump

    /*
      F(i): min times of jump to i
      D(i): distance max of jump from i
      F(i+1) || F(i+2) || ... || F(i+ D(i)) = F(i) + 1
     */

    int length = nums.size();
    vector<int> minTimes(length, 0);
    vector<bool> visited(length, false);
    int i;

    int j = 0;
    minTimes[0] = 0;
    for (i = 0; i < length; i++) {
      for (j = 1; j <= nums[i]; j++) {
        if (i + j >= length) {
          break;
        }
        if (!visited[i + j] ||
            (visited[i + j] && minTimes[i + j] > minTimes[i] + 1)) {
          visited[i + j] = true;

          minTimes[i + j] = minTimes[i] + 1;
        }
      }
    }

    return minTimes[length - 1];
  }
};

int main() {
  vector<int> vec;
  vec.push_back(2);
  vec.push_back(3);
  vec.push_back(1);
  vec.push_back(1);
  vec.push_back(4);

  Solution so;
  int ret = so.jump(vec);
  cout << "ret:" << ret << endl;
  return 0;
}
